Hydra

Limit pamięci: 128 MB

Bituś dostał na urodziny grę komputerową o nazwie Niesamowite przygody Rycerza Bajtazara. Zabawa polega na kierowaniu postacią tytułowego rycerza, który przemierza królestwo Bajtocji i pomaga uciśnionym przez poczwary, poborców podatkowych i gradobicia. Bituś przeszedł już prawie całą grę, ale utknął na ostatnim poziomie, w którym Bajtazar walczy z wielkim morskim wężem - Bajtocką Hydrą.

Do walki z potworem Bajtazar używa swojego miecza. W grze dostępne są dwa rodzaje ciosów: rycerz może albo uciąć głowę węża, albo (co oczywiście wymaga więcej wysiłku) zmasakrować tę głowę. Jednakowoż ucięcie głowy węża, choć prostsze, powoduje, że w miejscu odcięcia z szyi węża odrastają nowe głowy. Wodny potwór zostanie pokonany dopiero wtedy, gdy Bajtazar pozbawi go wszystkich głów i żadna głowa nie będzie już mogła odrosnąć.

Bajtocka Hydra może mieć rodzajów głów, które będziemy oznaczali liczbami od 1 do . Na samym początku wąż ma jedną głowę rodzaju 1. Głowa rodzaju (dla ) charakteryzuje się następującymi cechami: liczbą machnięć miecza , które musi wykonać Bajtazar, aby uciąć tę głowę, liczbą machnięć miecza , która jest wymagana do zmasakrowania tej głowy, oraz listą rodzajów głów , które odrastają na miejsce głowy rodzaju po jej ucięciu.

Podpowiedz Bitusiowi, ile minimalnie machnięć mieczem należy wykonać, aby pokonać Hydrę.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę rodzajów głów Hydry. Kolejne wierszy opisuje poszczególne rodzaje głów; w -tym z tych wierszy opisana jest głowa rodzaju . Wiersz ten zaczyna się trzema liczbami całkowitymi , , (, ), po których następują liczby całkowite (). Suma liczb nie przekracza .

Wyjście

W jedynym wierszu wyjścia należy wypisać minimalną liczbę machnięć mieczem, która jest potrzebna, by wygrać grę.

Przykład

Dla danych wejściowych:

4
4 27 3 2 3 2
3 5 1 2
1 13 2 4 2
5 6 1 2

poprawną odpowiedzią jest:

26

Autor zadania: Tomasz Idziaszek.